public class Solution {
    // bfs 广度优先遍历  -----  dfs深度优先遍历
    public int[] levelOrder(TreeNode root) {
        if (root == null) return new int[0];  // 特殊情况
        ArrayList<Integer> res = new ArrayList<>(); // 创建一个存放结果的集合
        Queue<TreeNode> queue = new LinkedList<>(); // 用于遍历
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll(); // 出队
            res.add(node.val);
            if (node.left != null) queue.add(node.left); // 左节点入队
            if (node.right != null) queue.add(node.right); // 右节点入队
        }
        // 将集合转换成数组
        int[] result = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
}
// 先进先出

// 3
// 第一次 9 20
// 第二次 20 
// 第三次 15 7
// 第四次 7
// 第五次 此时队列已经没有值了

// res : 3 9 20 15 7